1. Field of the Invention
This invention relates in general to database management systems performed by computers, and in particular, to the optimization of joined table expressions during query processing in database management systems by extended access path selection.
2. Description of Related Art
Computer systems incorporating Relational DataBase Management System (RDBMS) software using a Structured Query Language (SQL) interface are well known in the art. The SQL interface has evolved into a standard language for RDBMS software and has been adopted as such by both the American Nationals Standard Institute (ANSI) and the International Standards Organization (ISO).
There are a number of well-known and widely-applied optimization methods for queries available in the prior art. Some examples of these optimization methods include Dynamic Programming, Greedy Algorithm, etc. Generally, these optimization methods attempt to find the best execution strategy for a query based on a cost estimation over a range of possible execution strategies in the search space.
Many SQL query compilation and optimization techniques use a parse tree or other representation. A query can be represented as a binary operator tree with operators as the intermediate tree nodes and table references as leaf tree nodes. A straightforward query execution plan is to perform the operators one by one from the bottom up of the tree. This is termed an access path selection.
While optimization via access path selection is well known, it has not been successfully applied to joined table expressions. Joined table expressions are found in FROM clauses of SELECT statements, and generally take the form of xe2x80x9ctable-reference join-operator table-reference ON join-condition.xe2x80x9d The join-operator can be INNER JOIN, LEFT OUTER JOIN, RIGHT OUTER JOIN or FULL OUTER JOIN, the table-reference represents a base table or intermediate result table, and the join-condition is a boolean expression that results in a true, false, or unknown value. More complex joined table expressions can be a sequence of simple joined table expressions combined by join operators, parentheses, and nested table expressions.
There is a need in the art for improved methods of optimizing joined table expressions and complex join operations. Specifically, there is a need in the art for improved methods of optimizing joined table expressions and complex join operations using access path selection.
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses a method, apparatus, and article of manufacture for analyzing a query and extending an access path selection for the query, in order to optimize joined table expressions and complex join operations in the query. The extension of the access path selection occurs in two phases: (1) an access path selection router analyzes and divides the query into portions, so that the overall access path selection is divided into smaller access path selections for processing by a join enumerator; and (2) the join enumerator is provided to handle joined table expressions and complex join operators, wherein the join enumerator can be continuously enhanced as more powerful query optimization techniques become available.